#pragma once
#include <iostream>
#include <vector>
#include <cmath>
#include<limits>
#include<fstream>
#include<string>
#include <algorithm>
#include <memory>
#include <cwchar>
#include <locale>
#include <codecvt>
#include<windows.h>
#include <thread>
#include <mutex>
#include <atomic>
#include <iterator> 
#include <chrono>
#include"Function.h"

using namespace std;

#undef max 

class UserInputDataProcessor {
private:
    struct FlightLine {
        int id;
        double x1, y1, x2, y2;

        pair<pair<double, double>, pair<double, double>> getBoundingBox() const {
            return {
                {min(x1, x2), min(y1, y2)},
                {
                    
                    (x1, x2), max(y1, y2)}
            };
        }

    };

    struct QueryPoint {
        double x, y;
    };

    struct KDNode {
        int id;
        FlightLine line;
        shared_ptr<KDNode> left;
        shared_ptr<KDNode> right;
        int axis;
        double splitValue;
        pair<pair<double, double>, pair<double, double>> bbox;

        KDNode(const FlightLine& line, int axis, double split)
            : id(line.id), line(line), left(nullptr), right(nullptr),
            axis(axis), splitValue(split), bbox(line.getBoundingBox()) {}

        void updateBoundingBox() {
            if (left) {
                bbox.first.first = min(bbox.first.first, left->bbox.first.first);
                bbox.first.second = min(bbox.first.second, left->bbox.first.second);
                bbox.second.first = max(bbox.second.first, left->bbox.second.first);
                bbox.second.second = max(bbox.second.second, left->bbox.second.second);
            }
            if (right) {
                bbox.first.first = min(bbox.first.first, right->bbox.first.first);
                bbox.first.second = min(bbox.first.second, right->bbox.first.second);
                bbox.second.first = max(bbox.second.first, right->bbox.second.first);
                bbox.second.second = max(bbox.second.second, right->bbox.second.second);
            }
        }
    };

    static const size_t PARALLEL_SORT_THRESHOLD;
    static const size_t PARALLEL_BUILD_THRESHOLD;

    struct AxisCompare {
        int axis;
        AxisCompare(int a) : axis(a) {}
        bool operator()(const FlightLine& a, const FlightLine& b) {
            auto bbA = a.getBoundingBox();
            auto bbB = b.getBoundingBox();
            double aVal = axis == 0 ? bbA.first.first : bbA.first.second;
            double bVal = axis == 0 ? bbB.first.first : bbB.first.second;
            return aVal < bVal;
        }
    };

    template<typename RandomIt, typename Compare>
    static void parallel_sort(RandomIt first, RandomIt last, Compare comp, bool parallel = true) {
        const size_t len = distance(first, last);
        if (len <= 1 || !parallel || len < PARALLEL_SORT_THRESHOLD) {
            sort(first, last, comp);
            return;
        }

        RandomIt middle = first + len / 2;
        thread leftThread(parallel_sort<RandomIt, Compare>, first, middle, comp, false);
        parallel_sort(middle, last, comp, false);
        leftThread.join();

        inplace_merge(first, middle, last, comp);
    }
    void searchKDTree(shared_ptr<KDNode> node, const QueryPoint& query, double& minSqDist, int& nearestId) const;
    pair<size_t, double> findSplit(vector<FlightLine>& flightLines, int axis) const;
    shared_ptr<KDNode> buildKDTreeParallel(vector<FlightLine>& flightLines, int depth = 0, bool parallel = true) const;
    double pointToLineSquaredDistance(double px, double py, const FlightLine& line) const;

    double pointToBBoxMinSquaredDistance(double px, double py, const pair<pair<double, double>, pair<double, double>>& bbox) const;
    void parallelSearch(const shared_ptr<KDNode>& root, const vector<QueryPoint>& queryPoints, size_t start, size_t end);
    void findNearestFlightLineParallel(const vector<FlightLine>& flightLines,const vector<QueryPoint>& queryPoints);

    //void parallelSearch(const shared_ptr<KDNode>& root, const vector<QueryPoint>& queryPoints, vector<int>& results, size_t start, size_t end) const;
    //vector<int> findNearestFlightLineParallel(const vector<FlightLine>& flightLines, const vector<QueryPoint>& queryPoints) const;




    int flightNum, queryPointNum;//飞行线数量与查询点数量
    vector < vector < wstring >> FlightData, QueryPointData;// , QueryPointData_Point;
    vector<int> results;// = findNearestFlightLine(flightLines, queryPoints);
    int currentLine;

    // CSV行分割辅助函数
    vector<wstring> splitCSVLine(const wstring& line);
    //TXT行分割辅助函数
    vector<wstring> splitTXTLine(const wstring& line);
    //    void splitTXTLine(const wstring& line, vector<wstring>& result);

    int readCSVFile(wifstream& file);

    int readTextFile(wifstream& file);

    void processFlightLine(int id, double x1, double y1, double x2, double y2);

    void processQueryPoint(int id, double x, double y);

    /*
    // 计算两点距离的平方（避免开方提高效率）
    double distanceSquared(double x1, double y1, double x2, double y2);

    ////暴力方法求解最近飞行线
    //void findNearestFlightLine(const vector<FlightLine>& flightLines, const vector<QueryPoint>& queryPoints);
    */




public:
    vector<FlightLine> FlightLines;
    vector<QueryPoint> QueryPoints;
    vector<FlightLine> DirectlyInputFlightLines;
    vector<QueryPoint> DirectlyInputQueryPoints;
    //int cs;

    UserInputDataProcessor();

    int getCurrentLine();

    void getFlightDataReference(vector<vector<wstring>>& newdata);

    void getQueryPointDataReference(vector<vector<wstring>>& newdata);

    void getQueryPointData_PointReference(vector<vector<wstring>>& newdata);

    //传入查询的的坐标(Px,Py)，已知飞行线的两个端点(Ax,Ay)和(Bx,By)，返回查询点到飞行线的垂足坐标
    // 返回值: 最近点坐标(x,y)
    std::pair<double, double> findClosestPointOnSegment(double Px, double Py,double Ax, double Ay,
        double Bx, double By) const;

    int readDataFile(wstring filePath);

    void finishDirectInput();
    //std::shared_ptr<KDNode> InsertFlightLine(std::shared_ptr<KDNode> node, const FlightLine& line, int depth = 0);
        // 共用的数据结构初始化
    void initDataStructures(
        int flight_num = -1,
        int query_point_num = -1,
        bool resizeFlightLines = true
    );


};
